/**
 * 排序算法
 * */ 
/**
 * 冒泡排序算法
 * 1. 采用双循环的方式，第一次循环整个数组，第二次循环剩余未处理的值
 * 2. 每次循环发现前值大于后值则交换他们的位置，每次第一轮循环结束就能将一个当前剩余值中最大的值移动到当前剩余的末尾
 * */ 
const bubbleSort = async function(array) {
  const len = array.length - 1

  for(let i = 0;i < len;i++) {
    for(let j = 0;j < len - i;j++) {
      if (array[j] > array[j + 1]) {
        await displacement(array, j)
      }
    }
  }

  return array
}

function displacement(array, j) {
  return new Promise((resolve) => {
    setTimeout(() => {
      let max = array[j]
      array[j] = array[j + 1]
      array[j + 1] = max
      console.log(array)
      resolve()
    }, 1000)
  })
}

const arr = [232,5,4657,8798,54,457,89,5,3,44,34,66876]

// console.log(bubbleSort(arr))

/**
 * 快速排序算法
 * 1. 选择数组中的一个值作为基准值（a），将大于 a 的值放置到 a 的右边。将小于 a 的值放置在左边
 * 2. 递归的进行上一步，完成排序
 * */ 
function speedSort1(array, begin, end) {
  if (begin < end) {
    const base = array[begin]
    let i = begin
    let j = end

    while (i < j) {
      while (i < j && array[j] > base) j--
      array[i] = array[j]
      while (i < j && array[i] <= base) i++
      array[j] = array[i]
    }

    array[i] = base
    speedSort(array, begin, i - 1)
    speedSort(array, i + 1, end)
  }

  return array
}

// 第二中实现方式
function speedSort2(array) {
  const base = array[0]
  const leftVal = []
  const rightVal = []

  if (array.length <= 1) return array
  array = array.slice(1, array.length)
  for(let i = 0,len = array.length;i < len;i++){
    const val = array[i]
    if (val <= base) {
      leftVal.push(val)
    } else if (val > base) {
      rightVal.push(val)
    }
  }

  return speedSort2(leftVal).concat(base, speedSort2(rightVal))
}

// console.log(speedSort1(arr, 0, arr.length - 1))
console.log(speedSort2(arr))

